package leetcode;

/**
 * 贪心算法：单调递增的数字
 */
public class Solution37 {
    class Solution {
        public int monotoneIncreasingDigits(int n) {
            String s = String.valueOf(n);
            char[] arr = s.toCharArray();
            int flag = s.length();
            //从后遍历 利用flag进行标记
            for(int i = s.length() - 1; i > 0;i--){
                if(arr[i-1] > arr[i]){
                    arr[i-1]--;
                    flag = i;
                }
            }

            for(int i = flag;i < arr.length;i++){
                arr[i] = '9';
            }
            return Integer.parseInt(String.valueOf(arr));
        }
    }
}
